package 动态规划;

public class RobotWalk {
    public static int ways1(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start, K, aim, N);
    }

    // 机器人当前来到位置是cur
    // 机器人还有rest步需要去走
    // 最终的目标是aim
    // 有哪一些位置？ 1-N
    // 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
    public static int process1(int cur, int rest, int aim, int N) {
        if (rest == 0) {  // 如果已经不要走，走完了！
            return cur == aim ? 1 : 0;
        }

        // rest > 0 ，还有步数要走
        if (cur == 1) {   // 1-->2
            return process1(2, rest - 1, aim, N);
        }
        if (cur == N) {   // N-->N-1
            return process1(N - 1, rest - 1, aim, N);
        }
        // 中间位置上
        return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
    }


    public static int ways2(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        // dp就是缓存表  从顶向下的动态规划（记忆化搜索）
        // dp[cur][rest] == -1    ----->  process2(cur,rest)之前没算过
        // dp[cur][rest] ！= -1    ----->  process2(cur,rest)之前算过，返回值存在 dp[cur][rest]中
        // (N+1) * (K+1)
        return process1(start, K, aim, N);
    }

    // cur 范围： 1~N
    // rest 范围： 0 ~ K
    public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {   // 算过了以后直接拿值
            return dp[cur][rest];
        }
        // 之前没算过
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = process2(2, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = process2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }


    // 最终动态规划的版本
    public static int ways3(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1;  // dp[...][0] = 0

        for (int rest = 1; rest <= K; rest++) {   // 列

            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {  // 行
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        return dp[start][K];
    }


}
